package leetcode.offer_two_special.dp;

import java.util.Arrays;

/**
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：nums 可以分割成 [1, 5, 5] 和 [11]
 * 既然可以平分，sum一定是个偶数
 * 0-1背包问题:可以转化为可不可以凑成sum/2
 * 如果可以，说明其他元素和也为sum/2
 *
 * @author mazouri
 * @create 2021-09-25 18:42
 */
public class _101_canPartition {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 2 != 0) return false;

        boolean[][] dp = new boolean[nums.length + 1][(sum / 2) + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i - 1][j];
                if (!dp[i][j]&&j>=nums[i-1]){
                    dp[i][j] = dp[i-1][j-nums[i-1]];
                }
            }
        }

        return dp[dp.length - 1][dp[0].length - 1];
    }

    public static void main(String[] args) {
        System.out.println(new _101_canPartition().canPartition(new int[]{1, 2, 5}));
    }
}
